Consecutive Edge-Colorings of Generalized θ-Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Consecutive Edge-Colorings of Generalized θ-Graphs

  • Conference paper
Computational Geometry, Graphs and Applications (CGGA 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7033))

  • 887 Accesses

Abstract

A proper edge-coloring of a graph G using positive integers as colors is said to be a consecutive edge-coloring if for each vertex the colors of edges incident form an interval of integers. Recently, Feng and Huang studied the consecutive edge-coloring of generalized θ-graphs. A generalized θ-graph is a graph consisting of m internal disjoint (u,v)-paths, where 2 ≤ m < ∞. This paper investigates a problem provided by Feng and Huang, and gives a positive answer to the problem, except two cases are left.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Asratian, A.S., Cassegren, C.J.: On interval edge colorings of (α,β)-biregular bipartite graphs. Discrete Math. 307, 1951–1956 (2006)

    Article  MathSciNet  Google Scholar 

  2. Asratian, A.S., Denley, T.M.J., Häggkviist, R.: Bipartite Graphs and Their Applications. Cambridge University Press, Cambridge (1998)

    Book  MATH  Google Scholar 

  3. Asratian, A.S., Kamalian, R.R.: Interval colorings of edges of a multigraph. Appl. Math. 5, 25–34 (1987) (in Russian)

    MathSciNet  Google Scholar 

  4. Asratian, A.S., Kamalian, R.R.: Investigation on interval edge-colorings of graphs. J. Combin. Theory Ser. B 62, 34–43 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Axenovich, M.A.: On interval colorings of planar graphs. Congr. Numer. 159, 77–94 (2002)

    MathSciNet  MATH  Google Scholar 

  6. Feng, Y., Huang, Q.: Consecutive edge-coloring of the generalized θ-graph. Discrete Appl. Math. 155, 2321–2327 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Giaro, K.: The complexity of consecutive Δ-coloring of bipartite graphs: 4 is easy, 5 is hard. Ars. Combin. 47, 287–300 (1997)

    MathSciNet  MATH  Google Scholar 

  8. Giaro, K., Kubale, M.: Compact scheduling of zero-one time operations in multistage system. Discrete Appl. Math. 145, 95–103 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Giaro, K., Kubale, M.: Consecutive edge-colorings of complete and incomplete Cartesian products of graphs. Congr. Numer. 128, 143–149 (1997)

    MathSciNet  MATH  Google Scholar 

  10. Giaro, K., Kubale, M., Malafiejski, M.: Compact scheduling in open shop with zero-one time operations. Infor. 37, 37–47 (1999)

    MATH  Google Scholar 

  11. Giaro, K., Kubale, M., Malafiejski, M.: Consecutive colorings of the edges of general graphs. Discrete Math. 236, 131–143 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Giaro, K., Kubale, M., Malafiejski, M.: On the deficiency of bipartite graphs. Discrete Appl. Math. 94, 193–203 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hansen, H.M.: Scheduling with minimum waiting periods. Master’s Thesis, Odense University, Odense, Denmark (1992) (in Danish)

    Google Scholar 

  14. Hanson, D., Loten, C.O.M.: A lower bound for interval colouring bi-regular bipartite graphs. Bull. Inst. Combin. Appl. 18, 69–74 (1996)

    MathSciNet  MATH  Google Scholar 

  15. Hanson, D., Loten, C.O.M., Toft, B.: On interval colourings of bi-regular bipartite graphs. Ars. Combin. 50, 23–32 (1998)

    MathSciNet  MATH  Google Scholar 

  16. Kamalian, R.R.: On interval colorings of complete bipartite graphs and trees. In: Proc. 8-th Conference on Theoretical Cybernetics of USSR, Gorkii, p. 1, pp. 145–146 (1988)

    Google Scholar 

  17. Kamalian, R.R.: Interval coloring of complete bipartite graphs and trees. Preprint of the Computer Center of the Academy Sciences of Armenian SSR, Yerevan (1989) (in Russian)

    Google Scholar 

  18. Kamalian, R.R.: Interval Edge-colorings of Graphs. Doctoral dissertation, Novosibirsk (1990)

    Google Scholar 

  19. Kubale, M.: The complexity of scheduling independent two-processor tasks on dedicated processors. Inform. Process. Lett. 24, 141–147 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  20. Pyatkin, A.V.: Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs. J. Graph Theory 47, 122–128 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  21. Sevastjanov, S.V.: On interval colorability of a bipartite graph. Metody Diskret. Analiz. 50, 61–72 (1990) (in Russian)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Shijiazhuang University, Shijiazhuang, 050035, Hebei, P.R. China

    Yongqiang Zhao

  2. Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan

    Gerard J. Chang

  3. Institute for Mathematical Sciences, National Taiwan University, Taipei, 10617, Taiwan

    Gerard J. Chang

  4. National Center for Theoretical Sciences, Taipei Office, Taiwan

    Gerard J. Chang

Authors
  1. Yongqiang Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gerard J. Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Institute of Education, Tokai University, 2-28-4 Tomigaya, Tokio, Shibuya-ku, Japan

    Jin Akiyama

  2. School of Computer Science and Technology, Dalian Maritime University, 116026, Dalian, China

    Jiang Bo

  3. Ibaraki University, Nakanarusawa, 316-8511, Hitachi, Ibaraki, Japan

    Mikio Kano

  4. Tokai University, 4-1-1 Kitakaname, 259-1292, Hiratsuka, Japan

    Xuehou Tan

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zhao, Y., Chang, G.J. (2011). Consecutive Edge-Colorings of Generalized θ-Graphs. In: Akiyama, J., Bo, J., Kano, M., Tan, X. (eds) Computational Geometry, Graphs and Applications. CGGA 2010. Lecture Notes in Computer Science, vol 7033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24983-9_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-24983-9_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-24982-2

  • Online ISBN: 978-3-642-24983-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics