Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles

DOI10.1016/J.DAM.2021.01.032MaRDI QIDQ2656965zbMATH OpenOpenAlexFDO

Authors Xiaozheng Chen, Xueliang Li

Publication date 17 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.14099

zbMATH Keywords

edge-colored graphcolor degreeproper cycleproperly vertex-pancyclicity

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: In an edge-colored graph $(G,c)$, let $d^c(v)$ denote the number of colors on the edges incident with a vertex $v$ of $G$ and $delt{a}^c(G)$ denote the minimum value of $d^c(v)$ over all vertices $vinV(G)$. A cycle of $(G,c)$ is called proper if any two adjacent edges of the cycle have distinct colors. An edge-colored graph $(G,c)$ on $ngeq3$ vertices is called properly vertex-pancyclic if each vertex of $(G,c)$ is contained in a proper cycle of length $ell$ for every $ell$ with $3leelllen$. Fujita and Magnant conjectured that every edge-colored complete graph on $ngeq3$ vertices with $delt{a}^c(G)geqfracn+12$ is properly vertex-pancyclic. Chen, Huang and Yuan partially solve this conjecture by adding an extra condition that $(G,c)$ does not contain any monochromatic triangle. In this paper, we show that this conjecture is true if the edge-colored complete graph contain no joint monochromatic triangles.

Recommendations

• Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles
• Properly colored cycles in edge-colored complete graphs without monochromatic triangle: a vertex-pancyclic analogous result
• Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic paths of length three
• Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs
• Edge colorings of complete graphs without tricolored triangles
• Edge‐colored complete graphs without properly colored even cycles: A full characterization
• Monochromatic-degree conditions for properly colored cycles in edge-colored complete graphs
• scientific article; zbMATH DE number 4049669
• scientific article; zbMATH DE number 1506501
• Properly coloured Hamiltonian paths in edge-coloured complete graphs without monochromatic triangles

Cites work

• scientific article; zbMATH DE number 4049453 (Why is no real title available?)
• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• A note on alternating cycles in edge-coloured graphs
• Almost Eulerian compatible spanning circuits in edge-colored graphs
• Alternating Hamiltonian cycles
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Chinese postman problem on edge-colored multigraphs
• Compatible spanning circuits in edge-colored graphs
• Exact approaches for the orderly colored longest path problem: performance comparison
• Hamiltonian circuits determining the order of chromosomes
• Optimal pathway reconstruction on 3D NMR maps
• Paths and trails in edge-colored graphs
• Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles
• Properly colored paths and cycles
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Properly coloured Hamiltonian paths in edge-coloured complete graphs
• Some Theorems on Abstract Graphs
• The orderly colored longest path problem -- a survey of applications and new algorithms
• The rainbow spanning forest problem
• Two heuristics for the rainbow spanning forest problem

Cited in

(10)

• Color neighborhood union conditions for proper edge-pancyclicity of edge-colored complete graphs
• Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic paths of length three
• Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs
• Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs
• Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs
• Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles
• Properly colored cycles in edge-colored complete graphs without monochromatic triangle: a vertex-pancyclic analogous result
• Properly colored 2-factors of edge-colored complete bipartite graphs
• Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three
• Vertex-pancyclism in edge-colored complete graphs with restrictions in color transitions

This page was built for publication: Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles

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