Coloring of pseudocubic graphs in three colors

DOI10.3103/S0278641919020079MaRDI QIDQ2287152zbMATHOpenAlexWikidataFDO

Authors M. V. Mel'nik, A. V. Astakhova, Svetlana N. Selezneva

Publication date 23 January 2020

Published in Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s0278641919020079

zbMATH Keywords

chromatic numbercubic graphsubcubic graphpolynomial algorithmdegree of vertex3-coloring of graphscoloring of verticespseudocubic graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Recommendations

• scientific article; zbMATH DE number 2089961
• Polychromatic 4-coloring of cubic bipartite plane graphs
• The b-chromatic number of cubic graphs
• Linear colorings of subcubic graphs
• COLORING ALGORITHMS ON SUBCUBIC GRAPHS

Cites work

• scientific article; zbMATH DE number 46669 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• 4-coloring \(H\)-free graphs when \(H\) is small
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Graph theory
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Some simplified NP-complete graph problems
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(12)

• Cyclic colorings of 3-polytopes with large maximum face size
• 3-colouring for dually chordal graphs and generalisations
• On 3-colorings of bipartitep-threshold graphs
• Voloshin's colourings of \(P_{3}\)-designs
• Three-edge-colouring doublecross cubic graphs
• 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs
• On 3-hued coloring of graphs
• Method of 3-colouring of graphs
• On pseudocomplete coloring of graphs
• Acyclic 3-coloring of generalized Petersen graphs
• 3-consecutive C-colorings of graphs
• A generalization of Tait coloring cubic graphs

This page was built for publication: Coloring of pseudocubic graphs in three colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287152)