iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00373-022-02583-y
Chords of 2-Factors in Planar Cubic Bridgeless Graphs | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Chords of 2-Factors in Planar Cubic Bridgeless Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We show that every edge in a 2-edge-connected planar cubic graph is either contained in a 2-edge-cut or is a chord of some cycle contained in a 2-factor of the graph. As a consequence, we show that every edge in a cyclically 4-edge-connected planar cubic graph with at least six vertices is contained in a perfect matching whose removal disconnects the graph. We obtain a complete characterization of 2-edge-connected planar cubic graphs that have an edge such that every 2-factor containing the edge is a Hamiltonian cycle, and also of those that have an edge such that the complement of every perfect matching containing the edge is a Hamiltonian cycle. Another immediate consequence of the main result is that for any two edges contained in a facial cycle of a 2-edge-connected planar cubic graph, there exists a 2-factor in the graph such that both edges are contained in the same cycle of the 2-factor. We conjecture that this property holds for any two edges in a 2-edge-connected planar cubic graph, and prove it in the case the graph is also bipartite. The main result is proved in the dual form by showing that every plane triangulation admits a vertex 3-coloring such that no face is monochromatic and there is exactly one specified edge between a specified pair of color classes.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data Availability

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

  1. Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B., Zumstein, P.: Polychromatic colorings of plane graphs. Discret. Comput. Geom. 42, 421–442 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barnette, D.W.: Conjecture 5. Recent Progress in Combinatorics. In: Tutte, W.T. (ed.) Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, p. 343. Academic Press, New York (1969)

  3. Diwan, A.A.: Disconnected 2-factors in planar cubic bridgeless graphs. J. Comb. Theory Ser. B 84, 249–259 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dvořák, Z., Král, D.: On planar mixed hypergraphs. Electron. J. Comb. 8, 23 (2001)

    MathSciNet  MATH  Google Scholar 

  5. Funk, M., Jackson, B., Labbate, D., Sheehan, J.: 2-Factor hamiltonian graphs. J. Comb. Theory Ser. B 87, 138–144 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  6. Häggkvist, R.: Ear decompositions of a cubic bridgeless graph and near \(P_4\)-decompositions of its deck. Electron. Notes Discret. Math. 34, 191–198 (2009)

    Article  MATH  Google Scholar 

  7. Hoffmann-Ostenhof, A.: 3-Edge-coloring conjecture. Open problem garden. http://garden.irmacs.sfu.ca/op/3_edge_coloring_conjecture. Accessed 28 Apr 2020

  8. Matsumoto, N., Noguchi, K., Yashima, T.: Cubic graphs having only \(k\) cycles in each 2-factor. Discuss. Math. Graph Theory. https://doi.org/10.7151/dmgt.2447

  9. Penaud, J.G.: Une propriété de bicoloration des hypergraphes planaires (in French). In: Colloque sur la Théorie des Graphes, Paris, 1974, vol. 17, pp. 345–349. Cahiers Centre Études Recherche Opér. Brussels (1975)

  10. Petersen, J.: Die theorie der regulären graphs. Acta Math. 15, 193–220 (1891)

    Article  MathSciNet  MATH  Google Scholar 

  11. Schönberger, T.: Ein Beweis des Petersenschen Graphensatzes. Acta Sci. Math. Szeged 7, 51–57 (1934)

    MATH  Google Scholar 

Download references

Acknowledgements

We thank the anonymous reviewers for the detailed comments and suggestions that helped in improving the presentation.

Funding

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai, 400076, India

    Ajit A. Diwan

Authors
  1. Ajit A. Diwan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ajit A. Diwan.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Diwan, A.A. Chords of 2-Factors in Planar Cubic Bridgeless Graphs. Graphs and Combinatorics 38, 177 (2022). https://doi.org/10.1007/s00373-022-02583-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-022-02583-y

Keywords

Mathematics Subject Classification

Search

Navigation