Back to Search
Start Over
Fractional Matchings, Component-Factors and Edge-Chromatic Critical Graphs
- Source :
- Graphs and Combinatorics. 37:559-580
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- The first part of the paper studies star-cycle factors of graphs. It characterizes star-cycle factors of a graph $G$ and proves upper bounds for the minimum number of $K_{1,2}$-components in a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of a graph $G$. Furthermore, it shows where these components are located with respect to the Gallai-Edmonds decomposition of $G$ and it characterizes the edges which are not contained in any $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of $G$. The second part of the paper proves that every edge-chromatic critical graph $G$ has a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor, and the number of $K_{1,2}$-components is bounded in terms of its fractional matching number. Furthermore, it shows that for every edge $e$ of $G$, there is a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor $F$ with $e \in E(F)$. Consequences of these results for Vizing's critical graph conjectures are discussed.<br />final version, 23 pages
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Critical graph
Matching (graph theory)
010102 general mathematics
0102 computer and information sciences
Edge (geometry)
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
010201 computation theory & mathematics
Bounded function
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Component (group theory)
Combinatorics (math.CO)
0101 mathematics
Computer Science - Discrete Mathematics
Mathematics
Subjects
Details
- ISSN :
- 14355914 and 09110119
- Volume :
- 37
- Database :
- OpenAIRE
- Journal :
- Graphs and Combinatorics
- Accession number :
- edsair.doi.dedup.....4f75e31a14c3f0b78d28b5b4d361c403