For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been wid...For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.展开更多
By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertain...By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertainment experience. However, many enabling applications in 5G-VANET rely on the efficient content sharing among mobile vehicles, which is a very challenging issue due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this paper, we investigate content prefetching and distribution in 5G-VANET. We first introduce an edge computing based hierarchical architecture for efficient distribution of large-volume vehicular data. We then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced traffic. The content requests of vehicles can be served by neighbors, which can improve the sharing efficiency and alleviate the burden of networks. Furthermore, we use a graph theory based approach to solve the content distribution by transforming it into a maximum weighted independent set problem. Finally, the proposed scheme is evaluated with a greedy transmission strategy to demonstrate its efficiency.展开更多
文摘For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.
基金the support of National Science and Technology Major Project of the Ministry of Science and Technology of China under Grant No.2016ZX03001025003the Natural Science Foundation of Beijing under Grant No.4181002+2 种基金the Natural Science Foundation of China under Grant No.91638204BUPT Excellent Ph.D. Students Foundation under Grant No.CX2018210Natural Sciences and Engineering Research Council (NSERC),Canada
文摘By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertainment experience. However, many enabling applications in 5G-VANET rely on the efficient content sharing among mobile vehicles, which is a very challenging issue due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this paper, we investigate content prefetching and distribution in 5G-VANET. We first introduce an edge computing based hierarchical architecture for efficient distribution of large-volume vehicular data. We then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced traffic. The content requests of vehicles can be served by neighbors, which can improve the sharing efficiency and alleviate the burden of networks. Furthermore, we use a graph theory based approach to solve the content distribution by transforming it into a maximum weighted independent set problem. Finally, the proposed scheme is evaluated with a greedy transmission strategy to demonstrate its efficiency.
