RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sib. Èlektron. Mat. Izv., 2006, Volume 3, Pages 428–440 (Mi semr218)  

This article is cited in 10 scientific papers (total in 10 papers)

Research papers

Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable

O. V. Borodina, A. N. Glebova, T. R. Jensenb, A. Raspaudc

a Institute of Mathematics, Novosibirsk, Russia
b Alpen-Adria Universität Klagenfurt, Institut für Mathematik, Austria
c Université Bordeaux I, France

Abstract: Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are proved to be $3$-colorable, which extends Grötzsch's theorem. We conjecture that planar graphs without $3$-cycles adjacent to cycles of length $3$ or $5$ are $3$-colorable.

Full text: PDF file (711 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
UDC: 519.172.2
MSC: 05C15
Received December 14, 2006, published December 23, 2006
Language: English

Citation: O. V. Borodin, A. N. Glebov, T. R. Jensen, A. Raspaud, “Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable”, Sib. Èlektron. Mat. Izv., 3 (2006), 428–440

Citation in format AMSBIB
\Bibitem{BorGleJen06}
\by O.~V.~Borodin, A.~N.~Glebov, T.~R.~Jensen, A.~Raspaud
\paper Planar graphs without triangles adjacent to cycles of length from~$3$ to~$9$ are $3$-colorable
\jour Sib. \`Elektron. Mat. Izv.
\yr 2006
\vol 3
\pages 428--440
\mathnet{http://mi.mathnet.ru/semr218}
\zmath{https://zbmath.org/?q=an:1119.05037}


Linking options:
  • http://mi.mathnet.ru/eng/semr218
  • http://mi.mathnet.ru/eng/semr/v3/p428

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. O. V. Borodin, A. O. Ivanova, “Planar graphs without triangular $4$-cycles are $3$-choosable”, Sib. elektron. matem. izv., 5 (2008), 75–79  mathnet  mathscinet
    2. Borodin O.V., Glebov A.N., Montassier M., Raspaud A., “Planar graphs without 5-and 7-cycles and without adjacent triangles are 3-colorable”, J. Combin. Theory Ser. B, 99:4 (2009), 668–673  crossref  mathscinet  zmath  isi  elib
    3. Borodin O.V., Glebov A.N., Raspaud A., “Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable”, Discrete Math., 310:20 (2010), 2584–2594  crossref  mathscinet  zmath  isi  elib
    4. Borodin O.V., Montassier M., Raspaud A., “Planar graphs without adjacent cycles of length at most seven are 3-colorable”, Discrete Math., 310:1 (2010), 167–173  crossref  mathscinet  zmath  isi  elib
    5. Borodin O.V., Glebov A.N., “Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable”, J. Graph Theory, 66:1 (2011), 1–31  crossref  mathscinet  zmath  isi  elib
    6. Yang Ch.-Y., Zhu X., “Cycle adjacency of planar graphs and 3-colourability”, Taiwanese J. Math., 15:4 (2011), 1575–1580  mathscinet  zmath  isi  elib
    7. Borodin O.V. Glebov A.N. Jensen T.R., “A Step Towards the Strong Version of Havel's Three Color Conjecture”, J. Comb. Theory Ser. B, 102:6 (2012), 1295–1320  crossref  mathscinet  mathscinet  zmath  isi  elib
    8. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  mathscinet  zmath  isi  elib
    9. Kang Y., Wang Y., “Distance Constraints on Short Cycles For 3-Colorability of Planar Graphs”, Graphs Comb., 31:5 (2015), 1497–1505  crossref  mathscinet  zmath  isi  elib
    10. Cohen-Addad V., Hebdige M., Kral D., Li Zh., Salgado E., “Steinberg'S Conjecture Is False”, J. Comb. Theory Ser. B, 122 (2017), 452–456  crossref  mathscinet  zmath  isi  scopus
  • Number of views:
    This page:373
    Full text:54
    References:36

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019