Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank

DOI10.1016/j.dam.2013.09.012zbMath1283.05226MaRDI QIDQ2636822

Publication date: 18 February 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2013.09.012

zbMATH Keywords

independence number; matching number; chromatic index; rank of graphs

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

On the relation between theH-rank of a mixed graph and the matching number of its underlying graph, Nullity of a graph in terms of path cover number, Bounds on the nullity, the H-rank and the Hermitian energy of a mixed graph, Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph, Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph, Relation between the inertia indices of a complex unit gain graph and those of its underlying graph, Bounds for the rank of a complex unit gain graph in terms of the independence number, An improved lower bound for the nullity of a graph in terms of matching number, Upper bounds of the energy of triangle-free graphs in terms of matching number, The relation between the H-rank of a mixed graph and the independence number of its underlying graph, The extremal graphs with respect to their nullity, Unnamed Item, Unnamed Item, Inertia indices of a complex unit gain graph in terms of matching number, Proof of a conjecture on the nullity of a graph, A survey of the maximal and the minimal nullity in terms of omega invariant on graphs, On the difference between the skew-rank of an oriented graph and the rank of its underlying graph, Characterization of graphs with given order, given size and given matching number that minimize nullity, Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\), On connected graphs of order \(n\) with girth \(g\) and nullity \(n-g\), Relation between the nullity of a graph and its matching number, An upper bound of the nullity of a graph in terms of order and maximum degree, The rank of a signed graph in terms of the rank of its underlying graph, Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph, Relationship between the rank and the matching number of a graph, Graphs \(G\) with nullity \(2c(G) + p(G) - 1\), The multiplicities of eigenvalues of a graph, The nullity of a graph with fractional matching number, On connected signed graphs with rank equal to girth, The rank of a signed graph, Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree, Relations between the inertia indices of a mixed graph and those of its underlying graph, The rank of a complex unit gain graph in terms of the matching number, Bounds for the rank of a complex unit gain graph in terms of its maximum degree, No signed graph with the nullity \(\eta(G,\sigma)=|V(G)|-2m(G)+2c(G)-1\), No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\), The leaf-free graphs with nullity \(2 c ( G ) - 1\), The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices, A sharp upper bound of the nullity of a connected graph in terms of order and maximum degree, Nullities of graphs with given order, matching number and cyclomatic number revisited, Bounds for the matching number and cyclomatic number of a signed graph in terms of rank, The rank of a complex unit gain graph in terms of the rank of its underlying graph, An upper bound for the nullity of a bipartite graph in terms of its maximum degree

Cites Work